182. Призыв в армию

Для похода на Азерот Оргриму Думхаммеру потребовался еще один отряд. На призыв явились n орков. Способности в ближнем бою и метании копья каждого из них Оргрим сразу же оценил. Теперь же он должен определить кого из них назначить солдатом-пехотинцем (grunt), а кого метателем-охотником за головами (headhunter). При этом, для того, чтобы отряд был боеспособным, необходимо, чтобы было в отряде было не менее g грунтов и не менее h хедхантеров. После определения каждого орка в какой-то тип войск, может быть определена сила этого отряда, как сумма способностей всех орков в назначенной им специализации.

Напишите программу, определяющую максимально возможную силу вновь призванного отряда.

Вход. В первой строке заданы три целых числа n, g, h (1 ≤ n ≤ 10000, 0 ≤ g, h ≤ n). Далее идут n строк, в каждой из которых записаны два целых числа в диапазоне от 0 до 10000 – способность соответствующего орка в ближнем бою и его способность в метании копья.

Выход. Выведите максимальную силу боеспособной армии, которая может быть создана из призывников. В случае невозможности создания армии, удовлетворяющей заданным условиям, выведите число -1.

Пример входа 1	Пример выхода 1
6 2 2 3 1 3 6 5 4 9 11 8 6 6 3	39
Пример входа 2	Пример выхода 2
4 0 0 1 2 2 1 3 4 4 3	12
Пример входа 3	Пример выхода 3
2 2 2 4 5 2 3	-1

РЕШЕНИЕ

жадный алгоритм

Анализ алгоритма

Отсортируем пары по убыванию разности между способностями grunt и headhunter. Первые g орков отнесем к grunt, последние h орков отнесем к headhunter. Остальным оркам назначаем ту специальность, способность по которой у них больше.

Пример

Для первого примера после сортировки характеристики орков будут следующими:

· Первые два орка будут сражаться в ближнем бою, их сила равна 6 + 8 = 14.

· Последние два орка будут метать копья, их сила равна 11 + 6 = 17.

· Остальных орков назначаем согласно их максимальной способности: 3 + 5 = 8.

· Максимальная сила армии равна 14 + 17 + 8 = 39.

Реализация алгоритма

Характеристики орков храним в массиве пар v.

vector<pair<int, int> > v;

Функция f является компаратором сортировки. Пары сортируются по убыванию разности между способностями grunt и headhunter.

int f(pair<int, int> a, pair<int, int> b)

{

return a.first - a.second > b.first - b.second;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d %d", &n, &g, &h);

for (i = 0; i < n; i++)

{

scanf("%d %d", &a, &b);

v.push_back({a, b});

}

Если g + h > n, то армию создать неозможно.

if (g + h > n)

{

printf("-1\n");

return 0;

}

Сортируем пары способностей орков.

sort(v.begin(), v.end(), f);

В переменной res подсчитываем максимальную силу боеспособной армии.

res = 0;

Первые g орков делаем grunt.

for (i = 0; i < g; i++)

res += v[i].first;

Последние h орков делаем headhunter.

for (i = v.size() - h; i < v.size(); i++)

res += v[i].second;

Остальным оркам назначаем ту специальность, способность по которой у них больше.

for (i = g; i < n - h; i++)

res += max(v[i].first, v[i].second);

Выводим максимальную силу боеспособной армии.

printf("%d\n", res);